#pragma once
#include <iostream>
#include <vector>
#include <utility>

namespace me
{
    template <typename Value>
    struct hashNode
    {
        Value _data;
        hashNode* _next;

        hashNode(const Value& val):_data(val), _next(nullptr) {}
    };

    // 因为迭代器中用到了哈希表，但迭代器在定义时，还没有定义哈希表，此时编译器向上查找找不到，就会报错
    // 所以需要对哈希表进行前置声明
    template <typename K, typename V, typename KeyOfV, typename hash>
    class __hash;

    template <typename K, typename V, typename Ref, typename Ptr, typename KeyOfV, typename hash>
    struct hashIterator
    {
        using node = hashNode<V>;
        using Self = hashIterator<K, V, Ref, Ptr, KeyOfV, hash>;
        using table = __hash<K, V, KeyOfV, hash>;

        node* _node; // 当前迭代器指向的节点
        table* _tb; // 哈希表

        hashIterator(const node* node, table* tb):_node(node), _tb(tb) {}

        // 走到下一个节点，如果下一个节点为空，则遍历桶，走到下一个不为空的桶；如果不为空，则访问下一个节点
        Self& operator++()
        {
            KeyOfV __kov; // 获取key值
            hash __hash;  // 将key值转为整型 

            // 下一个节点不为空
            if(_node->_next) {
                _node = _node->_next;
                return *this;
            }

            // 下一个节点为空，走到下一个不为空的桶
            // 1.计算当前所在桶
            size_t __bucket = __hash(__kov(_node->_data)) % _tb->_tables.size();

            // 2.走到下一个不为空的桶
            __bucket++;
            while(__bucket < _tb->_tables.size() && _tb->_tables[__bucket] == nullptr) {
                __bucket++;
            }

            // 3.判断是找到了不为空的桶，还是越界了
            if(__bucket >= _tb->_tables.size()) {
                _node = nullptr;
            }else {
                _node = _tb->_tables[__bucket];
            }
            return *this;
        }

        Ref operator*() const { return _node->_data; }
        Ptr operator->() const { return &_node->_data; }
        bool operator!=(const Self& other) const { return _node != other->_node; }
        bool operator==(const Self& other) const { return _node == other->_node; }
    };

    template <typename K, typename V, typename KeyOfV/*取出V中的key*/, typename hash/*将key值转换为整型*/>
    class __hash
    {
        friend hashIterator<K, V, V&, V*, KeyOfV, hash>;

        /* V的取值随上层变化而变化：如果上层是unordered_map，则V = std::pair<K, V>；反之，K*/
        using Node = hashNode<V>;
        using iterator = hashIterator<K, V, V&, V*, KeyOfV, hash>;
        using const_iterator = hashIterator<K, V, const V&, const V*, KeyOfV, hash>;
    public:
        // 迭代器相关接口
        iterator begin()
        {
            // 返回第一个不用空的桶的头节点
            for(auto& bucket : _tables) {
                if(bucket) {
                    return {bucket, this};
                }
            } 
            return end();
        }

        iterator end() { return {nullptr, this}; }

        const_iterator cbegin() const
        {
            // 返回第一个不用空的桶的头节点
            for(auto& bucket : _tables) {
                if(bucket){
                    return {bucket, this};
                }
            } 
            return cend();
        }
        const_iterator cend() const { return {nullptr, this}; }
    private:
        void destroy()
        {
            // 遍历哈希表，将所有不为空的桶中的每一个节点都删除
            for(auto& bucket : _tables) {
                Node* cur = bucket;

                while(cur) {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                bucket = nullptr;
            }
        }

    public:
        __hash()
            :_n(0) 
        {
            _tables.resize(10, nullptr);
        }

        ~__hash()
        {
            destroy();
            _n = 0;
        }

        __hash(const __hash& other)
        {
            std::vector<Node*> nt(other._tables.size(), nullptr);
            for(size_t i=0; i<other._tables.size(); i++) {

                Node* cur = other._tables[i];
                while(cur) {
                    Node* newnode = new Node(cur->_data);
                    if(nt[i] == nullptr) {
                        nt[i] = newnode;
                    }else {
                        newnode->_next = nt[i];
                        nt[i] = newnode;
                    }
                    cur = cur->_next;
                }
            }
            _tables.swap(nt);
            _n = other._n;
        }

        __hash& operator=(__hash other)
        {
            std::swap(_tables, other._tables);
            std::swap(_n, other._n);
            return *this;
        }

        std::pair<iterator, bool> insert(const V& data)
        {
            KeyOfV __kov;
            hash __hash;

            // 先判断该元素是否已经存在
            iterator exist = find(__kov(data));
            if(exist != end()) return { exist, false };

            // 负载因子 == 1，扩容
            if(_n == _tables.size()) {
                size_t newSize = (_tables.size() == 0) ? 10 : 2*_tables.size();
                std::vector<Node*> newtable(newSize);

                for(auto& bucket : _tables) {
                    if(!bucket) continue;

                    Node* cur = bucket;
                    while(cur) {
                        Node* next = cur->_next;

                        // 计算在新表中的映射位置，并插入到新表中
                        size_t pos = __hash(__kov(cur->_data)) % newSize;
                        cur->_next = newtable[pos];
                        newtable[pos] = cur;

                        // 走到下一个节点/下一个桶
                        cur = next;
                    }
                    bucket = nullptr;
                }

                // 将节点转移之后，交换哈希表
                _tables.swap(newtable);
            }

            // 1.根据哈希函数，计算该值对应的桶
            size_t bucket = __hash(__kov(data)) % _tables.size();
            // 2.头插到该桶即可
            Node* newnode = new Node(data);
            newnode->_next = _tables[bucket];
            _tables[bucket] = newnode;
            ++_n;
            return std::make_pair({newnode, this}, true);
        }

        iterator find(const K& key)
        {
            KeyOfV __kov;
            hash __hash;

            // 空表直接返回end
            if(_tables.empty()) return end();
            // 根据k值计算映射位置
            size_t pos = __hash(key) % _tables.size();
            if(!_tables[pos]) { return {nullptr, this}; }

            Node* cur = _tables[pos];
            while(cur) {
                if(__kov(cur->_data) == key) {
                    return { cur, this};
                }
                cur = cur->_next;
            }

            return {nullptr, this};
        }

        size_t erase(const K& key)
        {
            KeyOfV __kov;
            hash __hash;

            size_t pos = __hash(key) % _tables.size();
            Node* cur = _tables[pos];
            Node* prev = nullptr;
            while(cur) {
                if(__kov(cur->_data) == key) {
                    if(prev == nullptr) {
                        // 头节点
                        _tables[pos] = cur->_next;
                    }else {
                        //其余节点
                        prev->_next = cur->_next;
                    }

                    delete cur;
                    cur = nullptr;
                    --_n;
                    return 1;
                }
                prev = cur;
                cur = cur->_next;
            }
            return 0;
        }
    private:
        std::vector<Node*> _tables;
        size_t _n;
    };
}
